package com.sunny.l53;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {

    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public ArrayList<TreeNode> generateTrees(int n) {

        ArrayList<TreeNode> tList = new ArrayList<>();
        if(0 == n){
            tList.add(null);
            return tList;
        }else if(1 == n){
            TreeNode resNode = new TreeNode(1);
            tList.add(resNode);
            return tList;
        }

        ArrayList<Integer> list = new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        dfs(list, 0);


        for(ArrayList<Integer> tmpList: res){
            TreeNode tmpRoot = build(tmpList);
            tList.add(tmpRoot);
        }
        return tList;

    }

    //全排列
    public void dfs(ArrayList<Integer> list, int ind){
        if(ind == list.size()){
            ArrayList<Integer> tmp = new ArrayList<>(list);
            res.add(tmp);
        }
        for(int i=ind;i<list.size();i++){
//            boolean flag = false;
            if(ind > 0 && i == ind+1 && i < list.size()){
//                System.out.println(list.get(ind-1)+" "+list.get(ind)+" "+list.get(ind+1));
//                System.out.println((list.get(ind-1) - list.get(ind))*(list.get(ind-1) - list.get(ind+1)));
                if((list.get(ind-1) - list.get(ind))*(list.get(ind-1) - list.get(ind+1)) < 0){
//                    flag = true;
                    continue;
                }
            }
//            System.out.println(flag);
//            if(!flag)
            Collections.swap(list, ind, i);
            dfs(list, ind+1);
//            if(!flag)
            Collections.swap(list, ind, i);
        }
    }

    //建立二叉搜索树
    public TreeNode build(ArrayList<Integer> list){
        TreeNode root = new TreeNode(list.get(0));
        for(int i=1;i<list.size();i++){
            TreeNode node = root;
            while (true){
                if(node.val > list.get(i)){
                    if(null != node.left){
                        node = node.left;
                    }else{
                        node.left = new TreeNode(list.get(i));
                        break;
                    }
                }else if(node.val < list.get(i)){
                    if(null != node.right){
                        node = node.right;
                    }else{
                        node.right = new TreeNode(list.get(i));
                        break;
                    }
                }else{
                    break;
                }
            }
        }
        return root;
    }

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,3));

        Solution solution = new Solution();
        solution.dfs(list, 0);
        System.out.println(solution.res);

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; left = null; right = null; }
}
